package edu.cityu.cs.hk.datastructures;
import java.util.Iterator;
/**
 * A specialization of a generic DFS used to find a cycle in a graph.
 * @author Roberto Tamassia, Michael Goodrich, Eric Zamore
 */
//begin#fragment FindCycleDFS
public class FindCycleDFS extends DFS { // find a cycle from a start vertex
  protected List cycle; // sequence of edges of the cycle
  protected boolean done;
  protected Vertex cycleStart;
//end#fragment FindCycleDFS
  /**
   * Executes the DFS algorithm.
   * @param g Input graph
   * @param start Start vertex
   * @param info Unused variable (can be anything)
   * @return {@link Iterator} containing an alternating sequence of
   * vertices and edges starting and ending with the same vertex, or
   * an empty iterator if the graph contains no cycles.
   */
//begin#fragment FindCycleDFS
  public Object execute(Graph g, Vertex start, Object info) {
    init(g);
    cycle = new NodeList();
    done = false;
    dfsTraversal(start);
    // remove the vertices and edges from start to cycleStart
    if (!cycle.isEmpty() && start != cycleStart) {
      Iterator pos = cycle.positions();
      while (pos.hasNext()) {
	Position p = (Position) pos.next();
	cycle.remove(p);                     // remove vertex from cycle
	p = (Position) pos.next();
	Edge e = (Edge) p.element();         // remove edge from cycle
	cycle.remove(p);
	Vertex[] endv = g.endVertices(e);
	if ((endv[0] == cycleStart) || (endv[1] == cycleStart )) break;
      }
    }
    return cycle.elements(); // iterator of the vertices and edges of the cycle 
  }
  protected void startVisit(Vertex v) { cycle.insertLast(v); /* add v to cycle */ }
  protected void finishVisit(Vertex v) {
    cycle.remove(cycle.last());	// remove v from cycle
    if (!cycle.isEmpty()) cycle.remove(cycle.last()); // remove edge into v from cycle
  }
  protected void traverseDiscovery(Edge e, Vertex from) { cycle.insertLast(e); }
  protected void traverseBack(Edge e, Vertex from) {
    cycle.insertLast(e);		// back edge e creates a cycle
    cycleStart = G.opposite(from, e);
    cycle.insertLast(cycleStart);	// first vertex completes the cycle
    done = true;
  }
  protected boolean isDone() {  return done; } 
}
//end#fragment FindCycleDFS

